package a3_p04_ng_sw;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;


import org.jgrapht.GraphPath;
import org.jgrapht.WeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.GraphPathImpl;




public class AStar extends AbstractSearchAlgo {

    @Override
    public List getTheShortestWay() {
        return getPathEdgeList();
    }

    private WeightedGraph<Knoten, DefaultWeightedEdge> graph;
	private Knoten start,end;
	private GraphPath<Knoten, DefaultWeightedEdge> path;
	private List<String> test = new ArrayList<String>();
	
	public AStar(WeightedGraph<Knoten, DefaultWeightedEdge> graph, Knoten start, Knoten end) {
		
		this.graph=graph;
		this.start=start;
		this.end=end;		
		aStarAlgo();
	}

	private void aStarAlgo() {
		 if (!graph.containsVertex(end))
	            throw new IllegalArgumentException("graph must contain the end vertex");
		 
		 List<Knoten> closedSet = new ArrayList<Knoten>(),
	        		  openSet   = new ArrayList<Knoten>();
		 
		 Map<Knoten,Knoten>  cameFrom = new HashMap<Knoten,Knoten>();
		 Map<Knoten, Double> gScoreMap = new HashMap<Knoten, Double>();
	     openSet.add(start);
	     TreeMap<Knoten, Double> fScoreMap = new TreeMap<Knoten, Double>(new KnotenComparator(graph, end));
	     gScoreMap.put(start, 0.0);
	     fScoreMap.put(start, (double) start.getKnotenarttibutt());
	     
	     while(!openSet.isEmpty()){
	    	 Knoten current =  fScoreMap.firstKey();
	    	 fScoreMap.remove(current);
	         openSet.remove(current);
	         closedSet.add(current);
	         for(DefaultWeightedEdge edge : graph.edgesOf(current)){
	        	 
	        	Knoten neighbor = graph.getEdgeTarget(edge);
	        	if(closedSet.contains(neighbor))
	        		continue;
	        	
	        	double tentativeGScore = gScoreMap.get(current) + graph.getEdgeWeight(graph.getEdge(current, neighbor));
	        	if(!openSet.contains(neighbor) || tentativeGScore < gScoreMap.get(neighbor)){
        			if(!openSet.contains(neighbor))
        				openSet.add(neighbor);
        			cameFrom.put(neighbor, current);
        			gScoreMap.put(neighbor, tentativeGScore);
        			neighbor.setfskore(gScoreMap.get(neighbor) + neighbor.getKnotenarttibutt());
        			fScoreMap.put(neighbor, gScoreMap.get(neighbor) + neighbor.getKnotenarttibutt());
        			
        		}
	          }

	     	}
	     path = buildGraphPath(cameFrom, end, graph);
	}
	
	
	
	
	private List<Knoten> buildPath(Map<Knoten,Knoten> cameFrom, Knoten currentNode){
    	List<Knoten> path = cameFrom.containsKey(currentNode) ? 
    			buildPath(cameFrom, cameFrom.get(currentNode)) :
    			new ArrayList<Knoten>();
		path.add(currentNode);
		test.add(currentNode.getName());
		return path;
    }

    private GraphPath<Knoten, DefaultWeightedEdge> buildGraphPath(Map<Knoten,Knoten> cameFrom, Knoten currentNode,
    								WeightedGraph<Knoten, DefaultWeightedEdge> graph){
    	List<Knoten> reconstructed = buildPath(cameFrom, currentNode);
		List<DefaultWeightedEdge> edgeList = new ArrayList<DefaultWeightedEdge>();
		double weight = 0.0;
		for(int i=0; i<reconstructed.size()-1; i++){
			DefaultWeightedEdge edge = graph.getEdge(reconstructed.get(i), reconstructed.get(i+1));
			weight += graph.getEdgeWeight(edge);
			edgeList.add(edge);
		}
		return new GraphPathImpl<Knoten, DefaultWeightedEdge>(graph, start, end, edgeList, weight);
    }
	
	
	
	public List<DefaultWeightedEdge> getPathEdgeList()
    {
        if (path == null) {
            return null;
        } else {
            return path.getEdgeList();
        }
    }
	public GraphPath<Knoten, DefaultWeightedEdge> getPath()
    {
        return path;
    }
	 public double getPathLength()
	 {
	   if (path == null) {
	      return Double.POSITIVE_INFINITY;
	   } else {
	      return path.getWeight();
	   }
	 }
	 public List<String> getTest(){
		 return test;
	 }



 private class KnotenComparator implements Comparator<Knoten>{
	private final Knoten goal;
	private final WeightedGraph<Knoten, DefaultWeightedEdge> graph;
	private KnotenComparator(WeightedGraph<Knoten, DefaultWeightedEdge> graph, Knoten goal){
		
		this.goal = goal;
		this.graph= graph;
	}
	
	@Override public int compare(Knoten o1, Knoten o2) {
//		Double o1Distance = provider.getPathCost(o1, goal),
//		o2Distance = provider.getPathCost(o2, goal);
		Double o1Distance = (double) o1.getfskore(),
			   o2Distance = (double) o2.getfskore();
		
		
		return o1Distance.compareTo(o2Distance);
	}
}
}